package heap;

import array.Array;

import java.util.Random;

public class MaxHeap<E extends Comparable<E>> {

    private Array<E> data;

    public MaxHeap(){
        data = new Array<>();
    }

    public MaxHeap(int capacity){
        data = new Array<>(capacity);
    }

    public MaxHeap(E[] array){
        data = new Array(array);
        for (int i = parent(array.length -1); i >=0 ; i--) {
            siftDown(i);
        }
    }

    public int getSize(){
        return data.getSize();
    }

    public boolean isEmpty(){
        return data.isEmpty();
    }

    //返回完全二叉树的数组表示中,一个索引所表示的元素的父亲节点的索引
    public int parent(int index){
        if (index == 0) {
            throw new RuntimeException("index is 0");
        }
        return (index-1) / 2;
    }

    //返回完全二叉树的数组表示中,一个索引所表示的元素的左孩子节点的索引
    public int leftChild(int index){
        return (index << 1) + 1;
    }

    //返回完全二叉树的数组表示中,一个索引所表示的元素的右孩子节点的索引
    public int rightChild(int index){
        return (index << 1) + 2;
    }

    public void add(E e){
        data.addLast(e);
        siftUp(data.getSize()-1);
    }

    //数据上浮
    private void siftUp(int k){
        while (k > 0 && data.get(parent(k)).compareTo(data.get(k)) <0) {
            //元素交换位置
            data.swap(k,parent(k));
            //交换位置后更新当前的索引，用于下一次循环
            k = parent(k);
        }
    }

    //找到最大值
    public E findMax(){
        if (data.getSize() == 0) {
            throw new RuntimeException(" size is 0");
        }
        return data.get(0);
    }

    //取出最大值
    public E extractMax(){
        E max = findMax();
        //交换 最后一个元素 ，使它成为 根元素
        data.swap(0,data.getSize()-1);
        //删除 最后一个元素
        data.removeLast();
        //下沉
        siftDown(0);
        return max;
    }

    private void siftDown(int k){
        while (leftChild(k) < data.getSize()) {
            //左孩子索引 作为最大子节点  索引
            int j = leftChild(k);
            // j+1是右孩子索引，此处比较 左孩子和右孩子的 大小
            if (j + 1 < data.getSize() && data.get(j + 1).compareTo(data.get(j)) > 0) {
                j = rightChild(k);
            }
            //当前节点与 最大的子节点比较，若 大于子节点，不再下沉
            if (data.get(k).compareTo(data.get(j)) >= 0) {
                break;
            }
            //当前节点与 大于该节点的 子节点 互换位置。
            data.swap(k,j);
            //变换当前 节点的索引。
            k = j ;
        }
    }

    public E replace(E e){
        E max = findMax();
        data.set(0,e);
        //下沉
        siftDown(0);
        return max;
    }

   private static double testHeap(Integer[] testData,boolean isHeap){
       long start = System.nanoTime();
       MaxHeap<Integer> maxHeap;
       if (isHeap) {
           maxHeap = new MaxHeap<>(testData);
       }else{
           maxHeap = new MaxHeap<>();
           for (int num : testData) {
                maxHeap.add(num);
           }
       }
       int[] arr = new int[testData.length];
       for (int i = 0; i < testData.length; i++) {
            arr[i] = maxHeap.extractMax();
       }
       for (int i = 1; i < testData.length; i++) {
           if (arr[i - 1] < arr[i])
               throw new RuntimeException("Error");
       }
        System.out.println("test heap compelete");
        long end = System.nanoTime();
        return (end-start)/1000000000.0;
       }



    public static void main(String[] args) {
        int n = 1000000;
        MaxHeap<Integer> maxHeap = new MaxHeap();
        Random random = new Random();
        for (int i = 0; i < n; i++) {
            maxHeap.add(random.nextInt(Integer.MAX_VALUE));
        }
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = maxHeap.extractMax();
        }

        for (int i = 1; i < n; i++) {
            if (arr[i-1] < arr[i]) {
                throw new RuntimeException("Error");
            }
        }

        System.out.println("Test compelete");
    }

}
